package com.wlr.study.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author lerong.wang
 * @version 1.0.0
 * @description 求出最长好子序列 I
 * 给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中
 * 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
 * <p></p>
 * 请你返回 nums 中 好 子序列的最长长度。
 * @date 2024/9/6 11:28
 */
public class LeetCode3176 {
    public static int maximumLength(int[] nums, int k) {
        int ans = 0;
        int len = nums.length;
        int[][] dp = new int[len][51];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }

        for (int i = 0; i < len; i++) {
            dp[i][0] = 1;
            for (int l = 0; l <= k; l++) {
                for (int j = 0; j < i; j++) {
                    int add = nums[i] != nums[j] ? 1 : 0;
                    if (l - add >= 0 && dp[j][l - add] != -1) {
                        dp[i][l] = Math.max(dp[i][l], dp[j][l - add] + 1);
                    }
                }
                ans = Math.max(ans, dp[i][l]);
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        System.out.println(LeetCode3176.maximumLength(new int[]{1,2,3,4,5,1}, 1));
    }
}